# Author    :Dun_Hz
# Time      :2024/3/18 15:39
# 中序表达式 ————————> 后续表达式
from Stack import Stack
def infix_to_postfix(infix_exp):
    # 记录操作符的优先级，用字典保存
    prec = {}
    prec['*']=3
    prec['/']=3
    prec['+']=2
    prec['-']=2
    prec['(']=1

    op_stack = Stack()
    postfix_list = []           # 记录输出结果
    token_list = infix_exp.split()      #解析式-->单词列表
    # 如果是操作数，直接添加到输出结果
    # 如果是左括号，压入栈
    # 如果是右括号，反复弹出栈顶的操作符，并输出，直到碰到左括号
    # 如果是操作符，比较栈顶操作符的优先级，栈顶的优先级高，则弹出，直到栈顶的操作符优先级低于它，压入栈顶，
    for token in token_list:
        #碰到操作数，直接输出
        if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or token in '0123456789':
            postfix_list.append(token)
        # 左括号直接进栈
        elif token == '(':
            op_stack.push(token)
        # 右括号开始出栈，知道碰到左括号
        elif token == ')':
            top_token = op_stack.pop()
            while top_token != '(':
                postfix_list.append(top_token)
                top_token = op_stack.pop()
        # 碰到操作符
        else:
            while not op_stack.isEmpty() and prec[op_stack.peek()] >=prec[token]:       # 栈顶的优先级 大于扫描到的操作符优先级
                postfix_list.append(op_stack.pop())     # 就弹出来栈顶的操作符
            op_stack.push(token)
    while not op_stack.isEmpty():
        postfix_list.append(op_stack.pop())

    return ' '.join(postfix_list)

print(infix_to_postfix('( A + B ) * ( C + D )'))